/*
day288
2020.6.11
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution{
public:
	const long M = 1e9 + 7;
    int threeSumMulti(vector<int>& A, int target) {
        sort(A.begin(), A.end());
        int N = A.size();
        long res = 0;
        for (int i = 0; i < N - 2; ++i) {
            int t = target - A[i];
            if (t < 2 * A[i]) break;
            int l = i + 1;
            int r = N - 1;
            while (A[l] < A[r]) {
                if (A[l] + A[r] > t) {
                    --r;
                } else if (A[l] + A[r] < t) {
                    ++l;
                } else {
                    int tl = l;
                    int tr = r;
                    while (A[++l] == A[tl]);
                    while (A[--r] == A[tr]);
                    res += (l - tl) * (tr - r);
                    res %= M;
                }
            }
            if (A[l] == A[r] && A[l] + A[r] == t) {
                int d = r - l + 1;
                res += d * (d - 1) / 2;
                res %= M;
            }
        }
        return res;
    }
};


int main()
{
	return 0;
}

